Theoretical Computer Science

In 2002, Subhash Khot, Member (2003–04) in the School of Mathematics, proposed the Unique Games Conjecture (UGC), one of the most hotly debated questions in theoretical computer science. Subsequently, Khot; Irit Dveer Dinur, Betsey Lombard Overdeck Theory of Computing Professor; and three other IAS-affiliated collaborators offered a proof that comprises the most significant advance toward resolving it.

Catherine Eva Pfaff, Member in the School of Mathematics (2024–25), discusses the ways in which geometric group theorists and theoretical computer scientists at the Institute for Advanced Study approach mathematical constructions and learn from one another’s insights.

In a groundbreaking study, Pravesh Kothari, Visiting Professor (2024) in the School of Mathematics, and Peter Manohar, Member (2024–26) in the School, have transformed theoretical computer scientists’ knowledge of locally correctable codes (LCCs), showing that such codes must grow exponentially as the amount of original data increases.

Pravesh Kothari, Visiting Professor in the School of Mathematics (2024), describes his experiences of interacting with “celebrities” from the worlds of pure mathematics and computer science at the Institute for Advanced Study, and how these two fields strongly interconnect at IAS.

In 2019–20, Chris J. Maddison, Member in the School of Mathematics and a Senior Research Scientist at DeepMind, is developing methods for machine learning and exploring foundational questions about how learning from data is possible.

One of the key scientific contributions of the 20th century, Claude Shannon's "A Mathematical Theory of Communication” created the field of information theory in 1948. In addition to the impact of information theory on communications technology...

Differential privacy disentangles learning about a dataset as a whole from learning about an individual data contributor. Just now entering practice on a global scale, the demand for advanced differential privacy techniques and knowledge of basic...

In 2016, Avi Wigderson, Herbert H. Maass Professor in the School of Mathematics, celebrates his sixtieth birthday. The Institute for Advanced Study hosted a conference in honor of this occasion from October 5 through October 8, 2016, with scholars...

Many natural and social phenomena may be viewed as inherently computational; they evolve patterns of information that can be described algorithmically and studied through computational models and techniques. A workshop on the computational lens...

How do we navigate the vast amount of data at our disposal? How do we choose a movie to watch, out of the 75,000 movies available on Netflix? Or a new book to read, among the 800,000 listed on Amazon? Or which news articles to read, out of the...